package com.xcc.dataStructures.demo06_algorithm;

/**
 * 快排
 */
public class QuickSort {

    public static void main(String[] args) {
//        int[] arr = {32, 7, 12, 11, 90, 5, 1};
        int data = 80000000;//8000w数据
        int[] arr = new int[data];
        for (int i = 0; i < data; i++) {
            arr[i] = (int) (Math.random() * data);
        }
        long startTime = System.currentTimeMillis();
        quickSort(arr,0,arr.length-1);
        long endTime = System.currentTimeMillis();
        System.out.println("时长：" + ((endTime - startTime))); //大概耗时7484ms
//        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int left,int right){
        //获取第一個值 作为基准
        if (left < right) {
            int temp = arr[left];
            int l = left;
            int r = right;
            while (l < r) {
                //当右边的值小于基准值时退出循环
                while (l < r && arr[r] >= temp) {
                    r--;
                }
                //当左边的值大于基准值时退出循环
                while (l < r && arr[l] <= temp) {
                    l++;
                }
                //将左右两边的数进行交换
                if (l < r) {
                    int t = arr[l];
                    arr[l] = arr[r];
                    arr[r] = t;
                }
            }
            //再将此时的arr[l]与基准节点进行交换
            arr[left] = arr[l];
            arr[l] = temp;

            //最后将左边和右边分别进行对应的递归调用
            quickSort(arr,left,l-1);
            quickSort(arr,l+1,right);
        }
    }

}
